package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HJ36_红黑图 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/36.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static void Solution(Scanner in) {
        int N = in.nextInt();
        int E = in.nextInt();
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            int[] edge = new int[2];
            edge[0] = in.nextInt();
            edge[1] = in.nextInt();
            edges.add(edge);
        }
        int total = (int) Math.pow(2, N);
        int p = total;
        for (int i = 0; i < p; i++) {
            int temp = i;
            int[] fangan = new int[N];
            for (int j = 0; j < N; j++) {
                fangan[j] = temp % 2;
                temp /= 2;
            }
            for (int j = 0; j < E; j++) {
                int[] edge = edges.get(j);
                if (fangan[edge[0]] == 1 && fangan[edge[1]] == 1) {
                    total--;
                    break;
                }
            }
        }
        System.out.println(total);
    }
}
